
package domain.queue;

import java.util.concurrent.atomic.AtomicReference;

/**
 * @author igordv
 *
 */
public class ConcurrentLinkedQueue <E> extends AbstractConcurrentQueue<E>{

	private final QueueNode<E> dummy = new QueueNode<E>(null, null);
	private final AtomicReference<QueueNode<E>> head = new AtomicReference<QueueNode<E>>(dummy);
	private final AtomicReference<QueueNode<E>> tail = new AtomicReference<QueueNode<E>>(dummy);

	public void enqueue(E item) {
		QueueNode<E> newNode = new QueueNode<E>(item, null);
		while (true) {
			QueueNode<E> curTail = tail.get();
			QueueNode<E> tailNext = curTail.next.get();
			if (curTail == tail.get()) {
				if (tailNext != null) {                     
					// Queue in intermediate state, advance tail
					tail.compareAndSet(curTail, tailNext);   
				} else {
					// In quiescent state, try inserting new node
					if (curTail.next.compareAndSet(null, newNode)) { 
						// Insertion succeeded, try advancing tail
						tail.compareAndSet(curTail, newNode);        
						return;
					}
				}
			}
		}
	}

	public E dequeue(){
		QueueNode<E> curHead;
		QueueNode<E> curTail;
		QueueNode<E> headsNext;
		// Keep trying until Dequeue is done
		while (true){
			curHead = head.get(); 								// Read Head
			curTail = tail.get(); 								// Read Tail
			headsNext = curHead.next.get(); 					// Read Heads Next
			if(curHead == head.get()){							// Are head, tail, next consistent 
				if(curHead.next == curTail.next){				// Is queue empty or Tail falling behind
					if(headsNext.next == null){					// Is queue empty?
						return null;							// Queue is empty, couldn't dequeue
					}
					tail.compareAndSet(curTail, headsNext);		// Tail is falling behind, try to advance it
				}else{											// No need to deal with Tail
					E ans = headsNext.item;						// Read value before CAS, otherwise another dequeue might free the next node
					if (head.compareAndSet(curHead, headsNext)){// Try to swing the Head to the next node
						return ans;								// Dequeue is done
					}
				}
			}
		}

	}
}
